package com.zhugang.week13.dp;

/**
 * @program algorithms
 * @description: bages2ByBacktrack
 * @author: chanzhugang
 * @create: 2022/09/14 23:40
 */
public class Bages2ByBacktrack {

    /**
     * 二维费用背包模型
     * 回溯解决：
     *
     * @param i
     * @param cw
     * @param cv
     */
    private int maxV = Integer.MIN_VALUE;
    private int[] items = {2, 2, 4, 6, 3};
    private int[] values = {3, 4, 8, 9, 6};
    private int n = 5;
    private int w = 9;

    public void f(int i, int cw, int cv) {
        // 回溯模版：无法用备忘录，效率不高
        if (i == n || cw == w) {
            if (cv > maxV) {
                maxV = cv;
            }
            return;
        }
        // 不装
        f(i + 1, cw, cv);
        if (cw + items[i] <= w) {
            // 装
            f(i + 1, cw + items[i], cv + values[i]);
        }
    }

    public static void main(String[] args) {
        Bages2ByBacktrack bages2ByBacktrack = new Bages2ByBacktrack();
        bages2ByBacktrack.f(0, 0, 0);
        System.out.println(bages2ByBacktrack.maxV);
    }
}